Logic, Computation And Set Theory

• A $1 . 7 \quad$ B1.12

  Logic, Computation and Set Theory

  Part II, 2001

  (i) What is the Halting Problem? What is an unsolvable problem?

  (ii) Prove that the Halting Problem is unsolvable. Is it decidable whether or not a machine halts with input zero?

  comment

• B2.11

  Logic, Computation and Set Theory

  Part II, 2001

  Let $U$ be an arbitrary set, and $\mathcal{P}(U)$ the power set of $U$. For $X$ a subset of $\mathcal{P}(U)$, the dual $X^{\vee}$ of $X$ is the set $\{y \subseteq U:(\forall x \in X)(y \cap x \neq \emptyset)\}$.

  (i) Show that $X \subseteq Y \rightarrow Y^{\vee} \subseteq X^{\vee}$.

  Show that for $\left\{X_{i}: i \in I\right\}$ a family of subsets of $\mathcal{P}(U)$

  $$\left(\bigcup\left\{X_{i}: i \in I\right\}\right)^{\vee}=\bigcap\left\{X_{i}^{\vee}: i \in I\right\}$$

  (ii) Consider $S=\left\{X \subseteq \mathcal{P}(U): X \subseteq X^{\vee}\right\}$. Show that $S$, $\subseteq$ is a chain-complete poset.

  State Zorn's lemma and use it to deduce that there exists $X$ with $X=X^{\vee}$.

  Show that if $X=X^{\vee}$ then the following hold:

  $X$ is closed under superset; for all $U^{\prime} \subseteq U, X$ contains either $U^{\prime}$ or $U \backslash U^{\prime}$.

  comment

• A3.8 B3.11

  Logic, Computation and Set Theory

  Part II, 2001

  (i) Write down a set of axioms for the theory of dense linear order with a bottom element but no top element.

  (ii) Prove that this theory has, up to isomorphism, precisely one countable model.

  comment

• A4.8 B4.10

  Logic, Computation and Set Theory

  Part II, 2001

  What is a wellfounded relation, and how does wellfoundedness underpin wellfounded induction?

  A formula $\phi(x, y)$ with two free variables defines an $\in$-automorphism if for all $x$ there is a unique $y$, the function $f$, defined by $y=f(x)$ if and only if $\phi(x, y)$, is a permutation of the universe, and we have $(\forall x y)(x \in y \leftrightarrow f(x) \in f(y))$.

  Use wellfounded induction over $\in$ to prove that all formulæ defining $\in$-automorphisms are equivalent to $x=y$.

  comment

• A $1 . 7 \quad$ B1.12

  Logic, Computation and Set Theory

  Part II, 2002

  (i) State the Knaster-Tarski fixed point theorem. Use it to prove the Cantor-Bernstein Theorem; that is, if there exist injections $A \rightarrow B$ and $B \rightarrow A$ for two sets $A$ and $B$ then there exists a bijection $A \rightarrow B$.

  (ii) Let $A$ be an arbitrary set and suppose given a subset $R$ of $P A \times A$. We define a subset $B \subseteq A$ to be $R$-closed just if whenever $(S, a) \in R$ and $S \subseteq B$ then $a \in B$. Show that the set of all $R$-closed subsets of $A$ is a complete poset in the inclusion ordering.

  Now assume that $A$ is itself equipped with a partial ordering $\leqslant$.

  (a) Suppose $R$ satisfies the condition that if $b \geqslant a \in A$ then $(\{b\}, a) \in R$.

  Show that if $B$ is $R$-closed then $c \leqslant b \in B$ implies $c \in B$.

  (b) Suppose that $R$ satisfies the following condition. Whenever $(S, a) \in R$ and $b \leqslant a$ then there exists $T \subseteq A$ such that $(T, b) \in R$, and for every $t \in T$ we have (i) $(\{b\}, t) \in R$, and (ii) $t \leqslant s$ for some $s \in S$. Let $B$ and $C$ be $R$-closed subsets of $A$. Show that the set

  $$[B \rightarrow C]=\{a \in A \mid \forall b \leqslant a(b \in B \Rightarrow b \in C)\}$$

  is $R$-closed.

  comment

• B2.11

  Logic, Computation and Set Theory

  Part II, 2002

  Explain what is meant by a structure for a first-order language and by a model for a first-order theory. If $T$ is a first-order theory whose axioms are all universal sentences (that is, sentences of the form $\left(\forall x_{1} \ldots x_{n}\right) p$ where $p$ is quantifier-free), show that every substructure of a $T$-model is a $T$-model.

  Now let $T$ be an arbitrary first-order theory in a language $L$, and let $M$ be an $L$-structure satisfying all the universal sentences which are derivable from the axioms of $T$. If $p$ is a quantifier-free formula (with free variables $x_{1}, \ldots, x_{n}$ say) whose interpretation $[p]_{M}$ is a nonempty subset of $M^{n}$, show that $T \cup\left\{\left(\exists x_{1} \cdots x_{n}\right) p\right\}$ is consistent.

  Let $L^{\prime}$ be the language obtained from $L$ by adjoining a new constant $\widehat{a}$for each element $a$ of $M$, and let

  $$T^{\prime}=T \cup\left\{p\left[\widehat{a}_{1}, \ldots, \widehat{a}_{n} / x_{1}, \ldots, x_{n}\right] \mid p \text { is quantifier-free and }\left(a_{1}, \ldots, a_{n}\right) \in[p]_{M}\right\}$$

  Show that $T^{\prime}$ has a model. [You may use the Completeness and Compactness Theorems.] Explain briefly why any such model contains a substructure isomorphic to $M$.

  comment

• A3.8 B3.11

  Logic, Computation and Set Theory

  Part II, 2002

  (i) Explain briefly what is meant by the terms register machine and computable function.

  Let $u$ be the universal computable function $u(m, n)=f_{m}(n)$ and $s$ a total computable function with $f_{s(m, n)}(k)=f_{m}(n, k)$. Here $f_{m}(n)$ and $f_{m}(n, k)$ are the unary and binary functions computed by the $m$-th register machine program $P_{m}$. Suppose $h: \mathbb{N} \rightarrow \mathbb{N}$ is a total computable function. By considering the function

  $$g(m, n)=u(h(s(m, m)), n)$$

  show that there is a number $a$ such that $f_{a}=f_{h(a)}$.

  (ii) Let $P$ be the set of all partial functions $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. Consider the mapping $\Phi: P \rightarrow P$ defined by

  $$\Phi(g)(m, n)= \begin{cases}n+1 & \text { if } m=0, \\ g(m-1,1) & \text { if } m>0, n=0 \text { and } g(m-1,1) \text { defined } \\ g(m-1, g(m, n-1)) & \text { if } m n>0 \text { and } g(m-1, g(m, n-1)) \text { defined }, \\ \text { undefined } & \text { otherwise. }\end{cases}$$

  (a) Show that any fixed point of $\Phi$ is a total function $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. Deduce that $\Phi$ has a unique fixed point.

  [The Bourbaki- Witt Theorem may be assumed if stated precisely.]

  (b) It follows from standard closure properties of the computable functions that there is a computable function $\psi$ such that

  $$\psi(p, m, n)=\Phi\left(f_{p}\right)(m, n) .$$

  Assuming this, show that there is a total computable function $h$ such that

  $$\Phi\left(f_{p}\right)=f_{h(p)} \text { for all } p .$$

  Deduce that the fixed point of $\Phi$ is computable.

  comment

• A4.8

  Logic, Computation and Set Theory

  Part II, 2002

  Let $P$ be a set of primitive propositions. Let $L(P)$ denote the set of all compound propositions over $P$, and let $S$ be a subset of $L(P)$. Consider the relation $\preceq$ on $L(P)$ defined by

  $$s \preceq s t \text { if and only if } S \cup\{s\} \vdash t .$$

  Prove that $\preceq_{S}$ is reflexive and transitive. Deduce that if we define $\approx_{S}$ by $\left(s \approx_{S} t\right.$ if and only if $s \preceq_{S} t$ and $\left.t \preceq \preceq_{S} s\right)$, then $\approx_{S}$ is an equivalence relation and the quotient $B_{S}=L(P) / \approx_{S}$ is partially ordered by the relation $\leqslant_{S}$ induced by $\preccurlyeq_{S}$ (that is, $[s] \leqslant_{S}[t]$ if and only if $s \preccurlyeq_{S} t$, where square brackets denote equivalence classes).

  Assuming the result that $B_{S}$ is a Boolean algebra with lattice operations induced by the logical operations on $L(P)$ (that is, $[s] \wedge[t]=[s \wedge t]$, etc.), show that there is a bijection between the following two sets:

  (a) The set of lattice homomorphisms $B_{S} \rightarrow\{0,1\}$.

  (b) The set of models of the propositional theory $S$.

  Deduce that the completeness theorem for propositional logic is equivalent to the assertion that, for any Boolean algebra $B$ with more than one element, there exists a homomorphism $B \rightarrow\{0,1\}$.

  [You may assume the result that the completeness theorem implies the compactness theorem.]

  comment

• B4.10

  Logic, Computation and Set Theory

  Part II, 2002

  Explain what is meant by a well-ordering of a set.

  Without assuming Zorn's Lemma, show that the power-set of any well-ordered set can be given a total (linear) ordering.

  By a selection function for a set $A$, we mean a function $f: P A \rightarrow P A$ such that $f(B) \subset B$ for all $B \subset A, f(B) \neq \emptyset$ for all $B \neq \emptyset$, and $f(B) \neq B$ if $B$ has more than one element. Suppose given a selection function $f$. Given a mapping $g: \alpha \rightarrow[0,1]$ for some ordinal $\alpha$, we define a subset $B(f, g) \subset A$ recursively as follows:

  $$\begin{aligned} &B(f, g)=A \quad \text { if } \alpha=0, \\ &B(f, g)=f\left(B\left(f,\left.g\right|_{\beta}\right)\right) \quad \text { if } \alpha=\beta^{+} \text {and } g(\beta)=1 \\ &B(f, g)=B\left(f,\left.g\right|_{\beta}\right) \backslash f\left(B\left(f,\left.g\right|_{\beta}\right)\right) \quad \text { if } \alpha=\beta^{+} \text {and } g(\beta)=0 \\ &B(f, g)=\bigcap\left\{B\left(f,\left.g\right|_{\beta}\right) \mid \beta<\alpha\right\} \quad \text { if } \alpha \text { is a limit ordinal. } \end{aligned}$$

  Show that, for any $x \in A$ and any ordinal $\alpha$, there exists a function $g$ with domain $\alpha$ such that $x \in B(f, g)$.

  [It may help to observe that $g$ is uniquely determined by $x$ and $\alpha$, though you need not show this explicitly.]

  Show also that there exists $\alpha$ such that, for every $g$ with domain $\alpha, B(f, g)$ is either empty or a singleton.

  Deduce that the assertion 'Every set has a selection function' implies that every set can be totally ordered.

  [Hartogs' Lemma may be assumed, provided you state it precisely.]

  comment

• A $1 . 7 \quad$ B1.12

  Logic, Computation and Set Theory

  Part II, 2003

  (i) State Zorn's Lemma. Use Zorn's Lemma to prove that every real vector space has a basis.

  (ii) State the Bourbaki-Witt Theorem, and use it to prove Zorn's Lemma, making clear where in the argument you appeal to the Axiom of Choice.

  Conversely, deduce the Bourbaki-Witt Theorem from Zorn's Lemma.

  If $X$ is a non-empty poset in which every chain has an upper bound, must $X$ be chain-complete?

  comment

• B2.11

  Logic, Computation and Set Theory

  Part II, 2003

  State the Axiom of Replacement.

  Show that for any set $x$ there is a transitive set $y$ that contains $x$, indicating where in your argument you have used the Axiom of Replacement. No form of recursion theorem may be assumed without proof.

  Which of the following are true and which are false? Give proofs or counterexamples as appropriate. You may assume standard properties of ordinals.

  (a) If $x$ is a transitive set then $x$ is an ordinal.

  (b) If each member of a set $x$ is an ordinal then $x$ is an ordinal.

  (c) If $x$ is a transitive set and each member of $x$ is an ordinal then $x$ is an ordinal.

  comment

• A3.8 B3.11

  Logic, Computation and Set Theory

  Part II, 2003

  (i) What does it mean for a function from $\mathbb{N}^{k}$ to $\mathbb{N}$ to be recursive? Write down a function that is not recursive. You should include a proof that your example is not recursive.

  (ii) What does it mean for a subset of $\mathbb{N}^{k}$ to be recursive, and what does it mean for it to be recursively enumerable? Give, with proof, an example of a set that is recursively enumerable but not recursive. Prove that a set is recursive if and only if both it and its complement are recursively enumerable. If a set is recursively enumerable, must its complement be recursively enumerable?

  [You may assume the existence of any universal recursive functions or universal register machine programs that you wish.]

  comment

• A4.8 B4.10

  Logic, Computation and Set Theory

  Part II, 2003

  Write an essay on propositional logic. You should include all relevant definitions, and should cover the Completeness Theorem, as well as the Compactness Theorem and the Decidability Theorem.

  [You may assume that the set of primitive propositions is countable. You do not need to give proofs of simple examples of syntactic implication, such as the fact that $p \Rightarrow p$ is a theorem or that $p \Rightarrow q$ and $q \Rightarrow r$ syntactically imply $p \Rightarrow r$.]

  comment

• A $1 . 7 \quad$ B1.12

  Logic, Computation and Set Theory

  Part II, 2004

  (i) State and prove the Knaster-Tarski Fixed-Point Theorem.

  (ii) A subset $S$ of a poset $X$ is called an up-set if whenever $x, y \in X$ satisfy $x \in S$ and $x \leqslant y$ then also $y \in S$. Show that the set of up-sets of $X$ (ordered by inclusion) is a complete poset.

  Let $X$ and $Y$ be totally ordered sets, such that $X$ is isomorphic to an up-set in $Y$ and $Y$ is isomorphic to the complement of an up-set in $X$. Prove that $X$ is isomorphic to $Y$. Indicate clearly where in your argument you have made use of the fact that $X$ and $Y$ are total orders, rather than just partial orders.

  [Recall that posets $X$ and $Y$ are called isomorphic if there exists a bijection $f$ from $X$ to $Y$ such that, for any $x, y \in X$, we have $f(x) \leqslant f(y)$ if and only if $x \leqslant y$.]

  comment

• B2.11

  Logic, Computation and Set Theory

  Part II, 2004

  Define the sets $V_{\alpha}, \alpha \in O N$. Show that each $V_{\alpha}$ is transitive, and explain why $V_{\alpha} \subseteq V_{\beta}$ whenever $\alpha \leqslant \beta$. Prove that every set $x$ is a member of some $V_{\alpha}$.

  Which of the following are true and which are false? Give proofs or counterexamples as appropriate. You may assume standard properties of rank.

  (a) If the rank of a set $x$ is a (non-zero) limit then $x$ is infinite.

  (b) If the rank of a set $x$ is a successor then $x$ is finite.

  (c) If the rank of a set $x$ is countable then $x$ is countable.

  comment

• A3.8 B3.11

  Logic, Computation and Set Theory

  Part II, 2004

  (i) State and prove the Compactness Theorem for first-order predicate logic.

  State and prove the Upward Löwenheim-Skolem Theorem.

  [You may use the Completeness Theorem for first-order predicate logic.]

  (ii) For each of the following theories, either give axioms (in the language of posets) for the theory or prove carefully that the theory is not axiomatisable.

  (a) The theory of posets having no maximal element.

  (b) The theory of posets having a unique maximal element.

  (c) The theory of posets having infinitely many maximal elements.

  (d) The theory of posets having finitely many maximal elements.

  (e) The theory of countable posets having a unique maximal element.

  comment

• A4.8 B4.10

  Logic, Computation and Set Theory

  Part II, 2004

  Write an essay on recursive functions. Your essay should include a sketch of why every computable function is recursive, and an explanation of the existence of a universal recursive function, as well as brief discussions of the Halting Problem and of the relationship between recursive sets and recursively enumerable sets.

  [You may assume that every recursive function is computable. You do not need to give proofs that particular functions to do with prime-power decompositions are recursive.]

  comment